1. Field of the Invention
This invention relates to the field of packet switching and packet routing and more particularly relates to packet forwarding.
2. Description of the Related Art
Generally, a router in a network uses routing tables to lookup a destination address to compute network routing and forward an incoming packet. Routing tables typically store millions of destination addresses for network hosts. Routing tables are periodically updated to reflect the active status of hosts in the network. When a packet arrives at the a router, the router extracts the destination information from packet header and searches the routing table for the destination route. Because the routing tables are based on conventional memory technology and contain a large amount of routing information, a search for the destination route can take significant amount of time and in some cases, may cause the router to drop the incoming packet due to certain timeout limits.
One method to resolve route lookup delay is to implement a route cache. Typically, a route cache is a software-based search table. A route cache is a comparatively smaller lookup table that stores the addresses of certain selected destinations (e.g., most frequently accessed destinations, recently accessed destinations and the like). When the router receives a packet, the router first searches the route cache for routing information and if the routing information is found in the route cache, the router forwards the packet to appropriate destination. Because the route cache is smaller, the search time is significantly less than the search time of larger lookup tables. The route cache is populated based on statistical and data traffic analysis done by each router in the network. A problem with software-based route caches is that the router keeps adding destination addresses to the route cache until the length of route cache reaches a certain maximum limit and the search efficiency starts degrading router's performance. The router then flushes the route cache (clears all the entries in the cache) and repopulates the route cache. The flushing and repopulating of the route cache causes additional delays for packet routing. This additional delay severely affects router performance and limits the maximum allowable throughput of the router.